package jiejie.qiye;

import java.util.*;

public class kuaiShou {
    static LinkedList<Integer> list = new LinkedList<>();
    public static void main(String[] args) {
        int[][] nums={{1,2,3},{4,5,6},{7,8,9}};
        //String s="abbassdfff";
        //String s="abcadsabcabc";
        //String t="abc";
        //System.out.println(findNum(nums,15));
        //findSum(6,1,6);
        //dczfc(s);
        //getLoc(s,t);
        //String s="akjsfhdq4435435''";
        //getwn(s);
        //String s="()(}){";
        //System.out.println(pipeikuohao(s));
        //int[] nums1={1,3,5,7,9};
        //int[] nums2={2,4,6,8};
        //System.out.println(getMidNum(nums1,nums2));
        System.out.println(zcbcfzc("helloworld"));
    }
    /**
     * 二维数组查找，从左到右从上到下增长
     * @param nums
     * @param target
     * @return
     */
    public static boolean findNum(int[][] nums, int target){
        if(nums==null||nums.length==0||nums[0].length==0)
            return false;
        int hs=nums.length;
        int ls=nums[0].length;
        int i=0;
        int j=ls-1;
        while(i<hs && j>=0){
            if(nums[i][j]==target)
                return true;
            else if(nums[i][j]>target)
                j--;
            else
                i++;
        }
        return false;
    }
    public static void findSum(int sum, int start, int end){
        if(sum<0 || start>end+1)
            return;
        if(sum==0){
            list.forEach(x -> System.out.print(x+" "));
            System.out.println();
        }
        if(sum>=start){
            list.push(start);
            findSum(sum-start,start+1,end);
            list.pop();
            findSum(sum,start+1,end);
        }
    }

    /**
     * 输出所有的对称子字符串，并输出最大子字符串长度
     * @param s
     */
    public static void dczfc(String s){
        if(s.length()==0)
            return;
        if(s.length()==1){
            System.out.println(s);
            System.out.println(1);
        }
        boolean flag;
        int res=Integer.MIN_VALUE;
        for(int i=0; i<s.length(); i++){
            for(int j=i+1; j<s.length(); j++){
                int l=i;
                int r=j;
                flag=true;
                while(l<r){
                    if(s.charAt(i)==s.charAt(j)){
                        l++;
                        r--;
                    }
                    else{
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    System.out.println(s.substring(i,j+1));
                    res=Math.max(res,j-i+1);
                }
            }
        }
        System.out.println(res);
    }

    /**
     * 获取t字符串内的开始和结束的位置
     * @param s
     * @param t
     */
    public static void getLoc(String s, String t){

        if(s.length()<t.length())
            return;

        for(int i=0; i<s.length()-t.length()+1; i++){
            String tmp=s.substring(i,i+t.length());
            if(tmp.equals(t)){
                System.out.println("start:"+i+"end:"+(i+t.length()-1));
            }
        }
    }

    /**
     * 字符串中字母的个数
     * @param s
     */
    public static void getwn(String s){
        int res=0;
        char[] arr=s.toCharArray();
        for (char c : arr) {
            if (Character.isLetter(c)) {
                res++;
            }
        }
        System.out.println(res);
    }

    /**
     * 有效的括号
     * @param s
     * @return
     */
    public static boolean pipeikuohao(String s){
        if(s.length()%2==1)
            return false;
        HashMap<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            if(map.containsKey(s.charAt(i))){
                if(stack.isEmpty() || stack.peek()!=map.get(s.charAt(i)))//peek()不删除栈顶的值pop()删除栈顶的值
                    return false;
                stack.pop();
            }
            else
                stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }

    /**
     * 合并两个数组求中位数
     * @param nums1
     * @param nums2
     * @return
     */
    public static int getMidNum(int[] nums1, int[] nums2){
        if(nums1==null || nums1.length==0)
            return getMidNum_helper(nums2);
        if(nums2==null || nums2.length==0)
            return getMidNum_helper(nums1);
        int len1=nums1.length;
        int len2=nums2.length;
        int[] new_nums=new int[len1+len2];
        int i=0;
        int j=0;
        int start=0;
        while(i<len1 && j<len2){
            if(nums1[i]<=nums2[j])
                new_nums[start++]=nums1[i++];
            else
                new_nums[start++]=nums2[j++];
        }

        while(i<len1){
            new_nums[start++]=nums1[i++];
        }
        while(j<len2){
            new_nums[start++]=nums2[j++];
        }
        System.out.println(Arrays.toString(new_nums));
        return getMidNum_helper(new_nums);

    }
    public static int getMidNum_helper(int[] nums){
        if(nums==null||nums.length==0)
            return -1;
        int mid=nums.length/2;
        return nums[mid];
    }
    public static String zcbcfzc(String s){
        if(s.length()<=1)
            return s;
        int len=s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i=0; i<len; i++)
            dp[i][i]=true;
        int res=0;
        int start=0;
        for(int j=1; j<len; j++) {
            for (int i=0; i<j; i++){
                if(dp[i+1][j] && dp[i][j-1] && s.charAt(i)!=s.charAt(j))
                    dp[i][j]=true;
                else
                    dp[i][j]=false;
                if(dp[i][j] && res<j-i+1){
                    res=j-i+1;
                    start=i;
                }
            }
        }
        for(int i=0; i<dp[0].length; i++)
            System.out.println(Arrays.toString(dp[i]));
        return s.substring(start,start+res+1);
    }
}
